package org.algorithm.熊猫.链表;

import org.algorithm.common.ListNode;
import org.algorithm.熊猫.链表.反转链表;
import org.junit.Test;


/**
 * @author jiazhaoxin
 * @Date 2022/2/12
 * @Desc {https://leetcode-cn.com/problems/reverse-linked-list-ii/}
 */
public class 反转链表2 {


    @Test
    public void test() {
        ListNode node = ListNode.build(1, 2);
        ListNode.print(node);
        System.out.println();

        node = reverseList2(node, 2, 2);
        ListNode.print(node);
    }

    /**
     * 截断子链表方法
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseList2(ListNode head, int left, int right) {

        //创建哨兵头节点
        ListNode dyNode = new ListNode(-99);
        dyNode.next = head;

        //确定子链表前驱节点
        ListNode pre = dyNode;
        for (int i = 0; i < left - 1; i++) {
            pre =pre.next;
        }

        //确定子链表后驱节点的前一个节点 right
        ListNode rightNode = pre;
        for (int i = 0; i < right-left +1; i++) {
            rightNode =rightNode.next;
        }

        //确定子链表
        ListNode leftNode = pre.next;
        //记录后驱接节点
        ListNode succ = rightNode.next;
        //截断子链表
        rightNode.next = null;

        //反转子链表
        反转链表.reverseList(leftNode);

        //子链表与主链表合并
        pre.next = rightNode;
        leftNode.next=succ;
        return dyNode.next;
    }

    //TODO 头插法
}
